/**
 *使用最大堆来寻找数组序列中的最小的几个数 
 *不稳定的排序
 *堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)
 */

#define LChild(i)  (2*(i)+1)
#define RChild(i)  (2*(i)+2)

int Parent(int i)
{
	return (int) ((i)-1)/2;
}
void swap(int *x,int *y)
{
    int temp = *x;
    *x= *y;
    *y = temp;
    return;
}

void percolateDown(int * heap,int index,int num)//下滤
{
    int index2 ;
    while (index <num)
    {
        if (LChild(index)<num)
        {
            if (RChild(index)<num)
            {
                index2 = heap[LChild(index)]>=heap[RChild(index)]?LChild(index):RChild(index);
            }
            else
            {
                index2 = LChild(index);
            }

        }
        else
        {
            break;
        }

        if(heap[index] <heap[index2])
        {
            swap(&heap[index] ,&heap[index2]);
            index  = index2;
        }
        else
        {
            break;
        }

    }
}

void MaxHeap_Create(int * heap,int num)
{
	int i;
    for (i =num-1;i>=0;i--)
    {
        percolateDown(heap,i,num);
    }
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    if(arr ==0)
    {
        *returnSize =0;
        return 0;
    }
    if(k==0)
    {
        *returnSize = 0;
        return 0;
    }
    if(arrSize<=k)
    {
        *returnSize = arrSize;
        return arr;
    }
    int * min_k = malloc(sizeof(int)*k);
    int i=0;
    for (;i<k;i++)
    {
        min_k[i] = arr[i];
    }
    MaxHeap_Create (min_k,k);
    for(;i<arrSize;i++)
    {
        if (arr[i]<min_k[0])
        {
            min_k[0] = arr[i];
            percolateDown( min_k, 0,k);//下滤
        }
    }
    *returnSize = k;
    return min_k;

}